package com.mdnote.practice.array.brackets;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @author Rhythm-2019
 * @date 2020/10/2
 * @description 判断括号是否合法
 */
public class LeetCode20 {

    public boolean isValid_ugly(String s) {
        // 返回值

        // 特殊值返回
        if ("".equals(s) || s == null) {
            return true;
        }
        if (s.length() % 2 != 0) {
            return false;
        }
        // 初始化
        Stack<Character> characters = new Stack<>();
        //解决
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                characters.push(')');
            } else if (s.charAt(i) == '{') {
                characters.push('}');
            } else if (s.charAt(i) == '[') {
                characters.push(']');
            } else if (s.charAt(i) == ')') {
                if (!characters.isEmpty() && ')' == characters.peek()) {
                    characters.pop();
                } else {
                    return false;
                }
            } else if (s.charAt(i) == '}') {
                if (!characters.isEmpty() && '}' == characters.peek()) {
                    characters.pop();
                } else {
                    return false;
                }
            } else if (s.charAt(i) == ']') {
                if (!characters.isEmpty() && ']' == characters.peek()) {
                    characters.pop();
                } else {
                    return false;
                }
            } else {
                return false;
            }
        }
        // 返回
        return characters.isEmpty();
    }

    public static void main(String[] args) {
        LeetCode20 leetCode20 = new LeetCode20();
        System.out.println(leetCode20.isValid("(((}))"));
    }

    public boolean isValid(String s) {

        HashMap<Character, Character> map = new HashMap<>();
        map.put('(', ')');
        map.put('[', ']');
        map.put('{', '}');

        LinkedList<Character> stack = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                stack.push(map.get(c));
            } else {
                if (stack.isEmpty() || stack.pop() != c) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}
